package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 赫夫曼树编码:
 * 赫夫曼编码是用于数据的压缩,原始的一个字符是8 bit,而赫夫曼编码是使用少量的bit来代表这8个bit
 * 从而完成数据的压缩,但赫夫曼编码有一个限制,我们知道8 bit代表的数字是-128 ~ 127之间,而在数据传输时
 * 又只能使用二进制数据,这样的话,如果有一个数据比较大,且内部的数据从-128 ~ 127都有,这样使用赫夫曼编码
 * 进行压缩时由于它也是使用二进制来代替这些字节,且保证每个都不会是前缀,这样的话几乎跟元数据大小是相同的,
 * 也就无法实现数据的压缩了,但对于文本类是可以实现数据压缩的,因为英文对应的byte值在67 ~ 123之间,并不会
 * 占用-128 ~ 127的范围有多大,而中文当数据量大且文字种类多时还需进行测试
 */
public class HuffmamBianMaDomo {
	public static void main(String[] args) throws IOException {
		//对文本进行压缩
		String data = "我的世界,你不明白,你知道吗?不知道就别说话,真是的,真不让人省心!";
		
		//创建赫夫曼编码类,将字节数组传入,用来压缩数据
		HuffmanEncoding encoding = new HuffmanEncoding(data.getBytes());
		//获取压缩后的字节数组
		byte[] by = encoding.getHuffmanEncodingBytes();
		/*
		 * 在这里打印压缩后的字节数长度,与原数据的字节数组长度对比可发现,当压缩的是文本数据时,
		 * 可以明显的看到数据的确被压缩了,但当传入图片的字节数组时,压缩的字节数组长度与原数据的
		 * 字节数组长度相比,几乎相同,并没有实现压缩
		 */
		System.out.println(by.length);
		//根据压缩的字节数组和解码表进行解码
		byte[] decoder = HuffmanEncoding.decoder(by, encoding.getDecodeMap());
		
		//将解压的数据进行还原
		//当是文本数据时
		System.out.println(new String(decoder));
		System.out.println("完毕");
	}
	
	@Test
	public void test(){
		//压缩文件
		/*String srcPath = "d://2.jpg";
		String drePath = "d://白色.zip";
		zip(srcPath,drePath);
		System.out.println("压缩完毕!!");*/
		//解压文件
		String srcPath1 = "d://白色.zip";
		String drePath1 = "d://3.jpg";
		unZip(srcPath1,drePath1);
		System.out.println("解压完毕!!");
	}
	
	//压缩文件的方法
	public void zip(String srcPath,String drePath){
		try (
				FileInputStream in = new FileInputStream(srcPath);
				OutputStream os = new FileOutputStream(drePath);
				ObjectOutputStream objOut = new ObjectOutputStream(os);
		) {
			byte[] b = new byte[in.available()];
			in.read(b);
			HuffmanEncoding hu = new HuffmanEncoding(b);
			byte[] huffmanBytes = hu.getHuffmanEncodingBytes();
			Map<String, Byte> decodeMap = hu.getDecodeMap();
			objOut.writeObject(huffmanBytes);
			objOut.writeObject(decodeMap);
		} catch (Exception e){
			e.printStackTrace();
		}
	}
	
	public void unZip(String srcPath,String drePath){
		try (
				FileInputStream in = new FileInputStream(srcPath);
				OutputStream os = new FileOutputStream(drePath);
				ObjectInputStream objIn = new ObjectInputStream(in);
		) {
			byte[] huffmanBytes = (byte[])objIn.readObject();
			Map<String, Byte> decodeMap = (Map<String, Byte>)objIn.readObject();
			byte[] decoder = HuffmanEncoding.decoder(huffmanBytes, decodeMap);
			os.write(decoder);
		} catch (Exception e){
			e.printStackTrace();
		}
	}
	
	//二叉树的Node节点
	class Node{
		int value;	//value为权值
		Byte b;		//b为保存的对应字节信息
		String bianma = "";	//每个字节对应的压缩后的编码
		Node left;	//左子节点
		Node right;	//右子节点
		
		//前序遍历
		public void perOrder(){
			System.out.println(this);
			if (this.left != null){
				this.left.perOrder();
			}
			if (this.right != null){
				this.right.perOrder();
			}
		}
		
		//查找:这里查找时,会同时生成该节点的编码信息,使用递归回溯实现
		public Node find(byte b){
			if (this == null || this.b == b){
				return this;
			}
			Node node = null;
			if (this.left != null) {
				this.left.bianma = this.bianma + "0";
				node = this.left.find(b);
			}
			if (node != null){
				return node;
			}
			if (this.right != null) {
				this.right.bianma = this.bianma + "1";
				node = this.right.find(b);
			}
			return node;
		}
		
		public Node(int value,Byte b) {
			this.value = value;
			this.b = b;
		}
		
		@Override
		public String toString() {
			return "Node{" +
					"value=" + value + "," + "byte=" + b +
					'}';
		}
	}
}

/*
 * 赫夫曼编码工具类:
 * 在创建该类对象时,就需要传入需要压缩的字节数组
 * 传入数据后,在创建对象的同时就会为该字节数组生成
 * 对应的赫夫曼树,并且生成对应的编码及解码
 * 在类中封装了返回压缩后的字节数组方法(getHuffmanEncodingBytes)
 * 获取编码(getEncodingMap)获取解码(getDecodeMap)
 * 及静态方法-对传入的赫夫曼编码和解码表进行解码(decoder)
 */
class HuffmanEncoding{
	private HuffmamBianMaDomo.Node root;
	private byte[] data;
	private Map<Byte,String> encodMap;
	private Map<String,Byte> decodeMap;
	//构造器
	public HuffmanEncoding (byte[] data){
		this.data = data;
		this.root = toHuffmanTree();
		encodMap = new HashMap<>();
		decodeMap = new HashMap<>();
		createEncodingAndDecodeMap(root,"","");
	}
	
	//对传入的字符串生成Node集合,并调用生成赫夫曼树
	/* 首先将传入的byte数组,循环遍历统计出每个字符出现的次数
	 * 在将其生成对应的二叉树节点其中每个字节出现的次数作为二叉树节点的权值
	 * byte字节对应权值生成Node节点,并放入list集合中,将list集合传入
	 * getHuffmanTree方法中,来生成赫夫曼树
	 */
	private HuffmamBianMaDomo.Node toHuffmanTree(){
		//使用map集合统计字符数量
		Map<Byte, Integer> zifu = new HashMap<>();
		byte[] bytes = data;
		for (int a = 0 ; a < bytes.length ; a ++){
			byte c = bytes[a];
			if (zifu.containsKey(c)){
				zifu.put(c,zifu.get(c) + 1 );
			}else{
				zifu.put(c,1);
			}
		}
		List<HuffmamBianMaDomo.Node> nodes = new ArrayList<>();
		HuffmamBianMaDomo h = new HuffmamBianMaDomo();
		//使用lamada表达式+stream流循环map集合将数据创建为Node节点并放入list集合中
		zifu.forEach((a,b) -> {
			nodes.add(h.new Node(b, a));
		});
		return getHuffmanTree(nodes);
	}
	
	//根据传入的Node集合,生成对应的赫夫曼树
	public HuffmamBianMaDomo.Node getHuffmanTree(List<HuffmamBianMaDomo.Node> nodes){
		HuffmamBianMaDomo h = new HuffmamBianMaDomo();
		//由于在里面会不停的对nodes进行remove操作,直到最后只剩下一个节点为止
		while (nodes.size() > 1) {
			//将集合进行排序,这里是从小到大排序
			nodes.sort((a, b) -> {
				return a.value - b.value;
			});
			//获取出权值最小的两个节点
			HuffmamBianMaDomo.Node leftNode = nodes.get(0);
			HuffmamBianMaDomo.Node rightNode = nodes.get(1);
			//获取出节点后,组成一个新的树
			HuffmamBianMaDomo.Node parent = h.new Node(leftNode.value + rightNode.value,null);
			parent.left = leftNode;
			parent.right = rightNode;
			//将集合中上面的两个节点删掉,再将parent加入集合中
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}
		//将头节点返回
		return nodes.get(0);
	}
	
	//根据对应的树生成对应的编码和解码
	private void createEncodingAndDecodeMap(HuffmamBianMaDomo.Node node, String code, String s){
		/*
		 * 在这里使用string而非StringBuffer的原因是,String是不可变字符串,而StringBuffer是可变字符串,
		 * 如果进行递归回溯的话,StringBuffer会将那一次的递归结果带出来,导致结果不准,如果要解决这个问题
		 * 可以在new StringBuffer(),但String在做+时也是new StringBuffer(),所以在这里直接使用
		 * String做+拼接字符串,看上去代码更简洁一些
		 */
		s += code;
		//判断node不为null时,再进行递归等等操作
		if (node != null) {
			//在此赫夫曼树中,节点有字节值的就是需要的节点,所以这里判断node.b == null,它为null时
			//表示还找到有byte值的节点,分别进行左右递归
			if (node.b == null) {
				//左递归
				createEncodingAndDecodeMap(node.left, "0", s);
				//右递归
				createEncodingAndDecodeMap(node.right, "1", s);
			} else {
				//找到了
				//将编码和字节存储到编码表和解码表中
				encodMap.put(node.b, s);
				decodeMap.put(s, node.b);
			}
		}
	}
	
	//获取编码
	public Map<Byte,String> getEncodingMap(){
		return encodMap;
	}
	
	//获取解码
	public Map<String,Byte> getDecodeMap(){
		return decodeMap;
	}
	
	//获取对应的赫夫曼压缩数据
	public byte[] getHuffmanEncodingBytes(){
		byte[] bytes = data;
		//将原始的字节按照赫夫曼编码编写成一个二进制字符串
		StringBuffer huffmanByte = new StringBuffer();
		for (byte c : bytes){
			huffmanByte.append(encodMap.get(c));
		}
		//转为byte
		//在将二进制的字符串转化为byte数组返回
		//首先确定byte数组的长度,每个byte字节为8位,所以这里使用上面得到的字符串长度 + 7再除以8
		byte[] huffmanbyte = new byte[(huffmanByte.length() + 7) / 8];
		String sub = "";
		//循环字符串,按8位一次进行循环
		for(int a = 0 ; a < huffmanByte.length() ; a += 8){
			//在截取出8位的二进制字符串
			if (a + 8 > huffmanByte.length()) {
				sub = huffmanByte.substring(a, huffmanByte.length());
			}else{
				sub = huffmanByte.substring(a, a + 8);
			}
			//将二进制字符串转化为byte字节,保存到创建的byte数组中
			huffmanbyte[a / 8] = (byte)Integer.parseInt(sub,2);
		}
		return huffmanbyte;
	}
	
	//解码
	public static byte[] decoder(byte[] b,Map<String,Byte> jiema){
		//创建一个StringBuilder来拼接保存赫夫曼编码的字节,将编码字节转化为字符串来操作
		StringBuilder s = new StringBuilder();
		String s1 = "";
		for (int a = 0 ; a < b.length ; a ++){
			//将byte转化为二进制的字符串,并进行补位,但数组中的最后一个字节,不进行补位
			if (a == b.length - 1) {
				s1 = Integer.toString(b[a] & 0xFF,2);
			} else {
				s1 = String.format("%8s", Integer.toBinaryString(b[a] & 0xFF)).replace(' ', '0');
			}
			s.append(s1);
		}
		//将上面得到的字符串进行循环,截取字符串的部分到解码表中进行匹配,没匹配到就多取一位
		//匹配到后就需要再对该位置后面的进行匹配
		int index = 0;
		ArrayList<Byte> bytes = new ArrayList<>(10000);
		for (int a = 1 ; a <= s.length() ; a ++){
			String sub = s.substring(index, a);
			Byte ch = jiema.get(sub);
			if (ch != null){
				bytes.add(ch);
				index = a;
			}
		}
		//将list中的字节转存到byte数组中
		byte[] bys = new byte[bytes.size()];
		for (int a = 0 ; a < bytes.size() ; a++){
			bys[a] = bytes.get(a);
		}
		return bys;
	}
}